Spanning Tree

定义 Definition

在图论中，“spanning tree（生成树）”指覆盖一个连通无向图的所有顶点、且不包含任何回路（环）的子图；它是一棵树，因此边数恰好为 n−1（n 为顶点数）。常用于网络设计、最小成本连线等问题。（也常见相关概念：minimum spanning tree，最小生成树。）

发音 Pronunciation (IPA)

/ˈspænɪŋ triː/

例句 Examples

A spanning tree connects all the nodes without cycles.
生成树把所有节点连接起来，但不包含任何环。

In network design, we often compute a spanning tree to ensure full connectivity while avoiding redundant links.
在网络设计中，我们常计算生成树，以保证完全连通，同时避免冗余连接。

词源 Etymology

spanning 来自动词 span（“跨越、覆盖”），表示“覆盖全部”；tree 在图论里借用“树”的形象，表示一种分支结构且无环的连通图。合起来 spanning tree 就是“覆盖全部顶点的树（结构）”，中文通常译为“生成树”。

相关词 Related Words

• Graph
• Vertex
• Edge
• Tree
• Cycle
• Connected
• Subgraph
• Minimum Spanning Tree
• Kruskal
• Prim

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在最小生成树（MST）章节系统讨论 spanning tree 与相关算法。
• Graph Theory（Bondy & Murty）：以图论基础的方式介绍生成树、树的性质与证明。
• Concrete Mathematics（Graham, Knuth, Patashnik）：在组合数学与图相关内容中涉及树与生成结构的计数与性质。